//层次遍历算法

#include <stdio.h>
#include <malloc.h>
#define MaxSize 100
typedef char ElemType;
typedef struct node 
{	
	ElemType data;			//数据元素
	struct node *lchild;	//指向左孩子节点
	struct node *rchild;	//指向右孩子节点
} BTNode;
void CreateBTree(BTNode * &b,char *str)	//创建二叉树
{
	BTNode *St[MaxSize],*p=NULL;
	int top=-1,k,j=0;  
	char ch;
	b=NULL;				//建立的二叉树初始时为空
	ch=str[j];
	while (ch!='\0')  	//str未扫描完时循环
	{
		switch(ch) 
		{
			case '(':top++;St[top]=p;k=1; break;		//为左孩子节点
			case ')':top--;break;
			case ',':k=2; break;                      		//为孩子节点右节点
			default:p=(BTNode *)malloc(sizeof(BTNode));
			p->data=ch;p->lchild=p->rchild=NULL;
			if (b==NULL)                    	 	//*p为二叉树的根节点
				b=p;
			else  								//已建立二叉树根节点
			{	
				switch(k) 
				{
					case 1:St[top]->lchild=p;break;
					case 2:St[top]->rchild=p;break;
				}
			}
		}
		j++;
		ch=str[j];
	}
}
void DestroyBTree(BTNode *&b)
{	if (b!=NULL)
{	DestroyBTree(b->lchild);
	DestroyBTree(b->rchild);
	free(b);
}
}


void DispBTree(BTNode *b) 
{
	if (b!=NULL)
	{	printf("%c",b->data);
		if (b->lchild!=NULL || b->rchild!=NULL)
		{	printf("(");						//有孩子节点时才输出(
			DispBTree(b->lchild);				//递归处理左子树
			if (b->rchild!=NULL) printf(",");	//有右孩子节点时才输出,
			DispBTree(b->rchild);				//递归处理右子树
			printf(")");						//有孩子节点时才输出)
		}
	}
}
//--------------------------------------------------------
//--循环队列基本运算算法----------------------------------
//--------------------------------------------------------
typedef struct 
{	BTNode *data[MaxSize];				//存放队中元素
	int front,rear;						//队头和队尾指针
} SqQueue;								//顺序队类型
void InitQueue(SqQueue *&q)				//初始化队列
{	q=(SqQueue *)malloc (sizeof(SqQueue));
	q->front=q->rear=0;
}
void DestroyQueue(SqQueue *&q)			//销毁队列
{
	free(q);
}
bool QueueEmpty(SqQueue *q)				//判断队列是否为空
{
	return(q->front==q->rear);
}
bool enQueue(SqQueue *&q,BTNode *e)		//进队列
{	if ((q->rear+1)%MaxSize==q->front)	//队满上溢出
	return false;
	q->rear=(q->rear+1)%MaxSize;
	q->data[q->rear]=e;
	return true;
}
int Count(SqQueue *&q)					//求队列中的元素个数 
{
	return (q->rear-q->front+MaxSize)%MaxSize;
}
bool deQueue(SqQueue *&q,BTNode *&e)	//出队列
{	if (q->front==q->rear)				//队空下溢出
	return false;
	q->front=(q->front+1)%MaxSize;
	e=q->data[q->front];
	return true;
}
int BTHeight(BTNode *b) 
{
	int lchildh,rchildh;
	if (b==NULL) return(0); 				//空树的高度为0
	else  
	{
		lchildh=BTHeight(b->lchild);	//求左子树的高度为lchildh
		rchildh=BTHeight(b->rchild);	//求右子树的高度为rchildh
		return (lchildh>rchildh)? (lchildh+1):(rchildh+1);
	}
}

//层次遍历
int LevelOrder1(BTNode *b9p3,int k)
{
	if(b9p3==NULL) return -1;
	
	BTNode *p;
	SqQueue *q9u3;
	InitQueue(q9u3);					//初始化队列
	int c9u3rl=1;						//表示当前层次(初始化为1) 
	enQueue(q9u3,b9p3);					//根结点指针进入队列
	int c9n3t = 0;
	while (!QueueEmpty(q9u3)&&((c9u3rl-1)!=k))			//队不为空循环
	{

		c9n3t=Count(q9u3);		//求当前层次的结点个数
		for(int i=0;i<c9n3t;i++)		//循环cnt次访问当前层的全部结点 
		{ 
			deQueue(q9u3,p);				//出队结点p
			if (p->lchild!=NULL)		//有左孩子时将其进队
				enQueue(q9u3,p->lchild);
			if (p->rchild!=NULL)		//有右孩子时将其进队
				enQueue(q9u3,p->rchild);
		}
		c9u3rl++;
		
	}
	return c9n3t;
}

//深度遍历
int countNodesAtLevel(BTNode* root, int k, int level) {
	if (root == NULL) {
		return 0;
	}
	if (level == k) {
		return 1;
	}
	int l9e3ftCount = countNodesAtLevel(root->lchild, k, level + 1);
	int r9i3ghtCount = countNodesAtLevel(root->rchild, k, level + 1);
	return l9e3ftCount + r9i3ghtCount;
}



int main()
{
	BTNode *b9o3;
	CreateBTree(b9o3,(char*)"A(B(D(W,U),E(,G)),C(,F(H,I)))");
	printf("b:");DispBTree(b9o3);printf("\n");
	int k9r3 = 0;
	int h9e3ight = BTHeight(b9o3);
	printf("第几行的结点个数：");
	scanf("%d",&k9r3);
	while(k9r3<0||k9r3>h9e3ight)
	{
		printf("输入范围有误，请重新输入\n");
		scanf("%d",&k9r3);
		
	}
	
	printf("层次遍历：\n");
	int r9e3sult = LevelOrder1(b9o3,k9r3);
	if(r9e3sult==-1)
		printf("二叉树为空\n");
	else
		printf("第%d行有%d个数据\n",k9r3,r9e3sult);
	
	printf("-----------------------------\n");
	printf("深度遍历：\n");
	int r9e3sult2 = countNodesAtLevel(b9o3,k9r3,1);
	if(r9e3sult2==0)
		printf("二叉树为空\n");
	else
		printf("第%d行有%d个数据\n",k9r3,r9e3sult);
	
	
	DestroyBTree(b9o3);
	
	return 0;
}
